package hanjia;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2025/2/14-下午12:56
 * Since  :   1.0
 * Version:   1.0
 */
public class LeetCode39 {

    public  List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> result = new ArrayList<>();
        List<List<Integer>> results =new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(candidates,target,result,results,0);
        return results;

    }

    private  void backtracking(int[] candidates, int target, List<Integer> result, List<List<Integer>> results,int start) {


        if (sum(result)>target){
            return;
        }
        if (sum(result)==target){
            results.add(new ArrayList<>(result));
        }


        for (int i=start;i<candidates.length;i++){
            if (candidates[i] > target) {

                break;
            }
            result.add(candidates[i]);
            backtracking(candidates,target,result,results,i);

            result.remove(result.size()-1);


        }
    }

    private int sum(List<Integer> result){
        int sum=0;
        for (int i:result){
            sum+=i;
        }
        return sum;
    }
}
